package binarysearch;

public class Solution378 {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        //区间最小值
        int left = matrix[0][0];
        //区间最大值
        int right = matrix[n-1][n-1];

        while(left<right){
            int mid = left + ((right - left) >> 1);;
            if (check(matrix,k,mid,n)){
                right=mid;
            }else {
                left = mid+1;
            }
        }

        return left;
    }

    public boolean check(int[][] matrix,int k,int mid,int n){
        int i = n-1;
        int j = 0;
        int count = 0;

        while(i>=0 && j<matrix[i].length){
            if (matrix[i][j]<=mid){
                count += i+1;
                j++;
            }else {
                i--;
            }
        }

        return count>=k;
    }
}
